<!DOCTYPE html>
    <html>
    <head>
        <meta charset="UTF-8">
        <title>bfs</title>
        <style>
</style>
        
        <link rel="stylesheet" href="https://cdn.jsdelivr.net/gh/Microsoft/vscode/extensions/markdown-language-features/media/markdown.css">
<link rel="stylesheet" href="https://cdn.jsdelivr.net/gh/Microsoft/vscode/extensions/markdown-language-features/media/highlight.css">
<style>
            body {
                font-family: -apple-system, BlinkMacSystemFont, 'Segoe WPC', 'Segoe UI', system-ui, 'Ubuntu', 'Droid Sans', sans-serif;
                font-size: 14px;
                line-height: 1.6;
            }
        </style>
        <style>
.task-list-item { list-style-type: none; } .task-list-item-checkbox { margin-left: -20px; vertical-align: middle; }
</style>
        
        
        
    </head>
    <body class="vscode-light">
        <h1 id="bfs">bfs</h1>
<h1 id="1-lc-310-minimum-height-trees">1. LC 310  Minimum Height Trees</h1>
<ul>
<li><a href="https://leetcode.com/problems/minimum-height-trees/">https://leetcode.com/problems/minimum-height-trees/</a></li>
</ul>
<p>A tree is an undirected graph in which any two vertices are connected by exactly one path. In other words, any connected graph without simple cycles is a tree.</p>
<p>Given a tree of n nodes labelled from 0 to n - 1, and an array of n - 1 edges where edges[i] = [ai, bi] indicates that there is an undirected edge between the two nodes ai and bi in the tree, you can choose any node of the tree as the root. When you select a node x as the root, the result tree has height h. Among all possible rooted trees, those with minimum height (i.e. min(h))  are called minimum height trees (MHTs).</p>
<p>Return a list of all MHTs' root labels. You can return the answer in any order.</p>
<p>The height of a rooted tree is the number of edges on the longest downward path between the root and a leaf.</p>
<pre><code><code><div>Example 1:

Input: n = 4, edges = [[1,0],[1,2],[1,3]]
Output: [1]
Explanation: As shown, the height of the tree is 1 when the root is the node with label 1 which is the only MHT.
</div></code></code></pre>
<p>我最开始的想法是bfs遍历所有节点, 取结果的最小集合。 但是会超时</p>
<p>官方答案， 只需要做一次bfs. 结合拓扑排序， 就是从只有一个邻居的点开始， 它们是叶子节点leaf。</p>
<p>挨个遍历leaf节点A, 把A 从图里面remove掉，同时添加A的邻居B，如果B的邻居也只有1个, B就是下一个叶子节点. 继续遍历，直到图里面只剩下1个或者2个节点。</p>
<pre><code class="language-python"><div><span class="hljs-class"><span class="hljs-keyword">class</span> <span class="hljs-title">Solution</span>:</span>
    <span class="hljs-function"><span class="hljs-keyword">def</span> <span class="hljs-title">findMinHeightTrees</span><span class="hljs-params">(self, n: int, edges: List[List[int]])</span> -&gt; List[int]:</span>

        <span class="hljs-comment"># base cases</span>
        <span class="hljs-keyword">if</span> n &lt;= <span class="hljs-number">2</span>:
            <span class="hljs-keyword">return</span> [i <span class="hljs-keyword">for</span> i <span class="hljs-keyword">in</span> range(n)]

        <span class="hljs-comment"># Build the graph with the adjacency list</span>
        neighbors = [set() <span class="hljs-keyword">for</span> i <span class="hljs-keyword">in</span> range(n)]
        <span class="hljs-keyword">for</span> start, end <span class="hljs-keyword">in</span> edges:
            neighbors[start].add(end)
            neighbors[end].add(start)

        <span class="hljs-comment"># Initialize the first layer of leaves</span>
        leaves = []
        <span class="hljs-keyword">for</span> i <span class="hljs-keyword">in</span> range(n):
            <span class="hljs-keyword">if</span> len(neighbors[i]) == <span class="hljs-number">1</span>:
                leaves.append(i)

        <span class="hljs-comment"># Trim the leaves until reaching the centroids</span>
        remaining_nodes = n
        <span class="hljs-keyword">while</span> remaining_nodes &gt; <span class="hljs-number">2</span>:
            remaining_nodes -= len(leaves)
            new_leaves = []
            <span class="hljs-comment"># remove the current leaves along with the edges</span>
            <span class="hljs-keyword">while</span> leaves:
                leaf = leaves.pop()
                <span class="hljs-comment"># the only neighbor left for the leaf node</span>
                neighbor = neighbors[leaf].pop()
                <span class="hljs-comment"># remove the only edge left</span>
                neighbors[neighbor].remove(leaf)
                <span class="hljs-keyword">if</span> len(neighbors[neighbor]) == <span class="hljs-number">1</span>:
                    new_leaves.append(neighbor)

            <span class="hljs-comment"># prepare for the next round</span>
            leaves = new_leaves

        <span class="hljs-comment"># The remaining nodes are the centroids of the graph</span>
        <span class="hljs-keyword">return</span> leaves
</div></code></pre>

    </body>
    </html>